#include "biTree.h"
#include "../linkstack/linkstack.h"

extern func_LinkStack fLinkStack;

/**
 * 功 能：
 *      二叉树的递归遍历 - 先序遍历
 * 参 数：
 *      root：要遍历的树
 * 返回值：
 *      无 
 **/
void Traversal_Before(BiTNode *root)
{
    if (root == NULL)
        return;
    // 遍历根节点
    printf("%c ", root->data);
    // 遍历左子树
    Traversal_Before(root->lchild);
    // 遍历右子树
    Traversal_Before(root->rchild);
}

/**
 * 功 能：
 *      创建并且初始二叉树 - 指针定义
 * 参 数：
 *      无
 * 返回值：
 *      无
 **/
void BiTree_Create(void)
{
    BiTNode *p1, *p2, *p3, *p4, *p5, *p6, *p7, *p8, *p9;

    p1 = (BiTNode *)malloc(sizeof(BiTNode));
    p2 = (BiTNode *)malloc(sizeof(BiTNode));
    p3 = (BiTNode *)malloc(sizeof(BiTNode));
    p4 = (BiTNode *)malloc(sizeof(BiTNode));
    p5 = (BiTNode *)malloc(sizeof(BiTNode));
    p6 = (BiTNode *)malloc(sizeof(BiTNode));
    p7 = (BiTNode *)malloc(sizeof(BiTNode));
    p8 = (BiTNode *)malloc(sizeof(BiTNode));
    p9 = (BiTNode *)malloc(sizeof(BiTNode));

    memset(p1, 0, sizeof(BiTNode));
    memset(p2, 0, sizeof(BiTNode));
    memset(p3, 0, sizeof(BiTNode));
    memset(p4, 0, sizeof(BiTNode));
    memset(p5, 0, sizeof(BiTNode));
    memset(p6, 0, sizeof(BiTNode));
    memset(p7, 0, sizeof(BiTNode));
    memset(p8, 0, sizeof(BiTNode));
    memset(p9, 0, sizeof(BiTNode));

    p1->data = 'A';
    p2->data = 'B';
    p3->data = 'C';
    p4->data = 'D';
    p5->data = 'E';
    p6->data = 'F';
    p7->data = 'G';
    p8->data = 'H';
    p9->data = 'I';

    /* 二叉树的关系式的创建 */
    p1->lchild = p2;
    p1->rchild = p3;
    p2->lchild = p4;
    p2->rchild = p5;
    p3->lchild = p6;
    p3->rchild = p7;

    p4->lchild = p8;
    p4->rchild = p9;

    /* 二叉树的遍历 */

    printf("Traversal_Before    : ");
    Traversal_Before(p1);
    putchar(10);
    printf("nonTraversal_Before : ");
    traversal.prev(p1);
    putchar(10);
    printf("%s Finished! \n", __func__);
}

/**
 * 功 能：
 *      二叉树的非递归遍历 - 先序遍历
 * 参 数：
 *      root：要遍历的树
 * 返回值：
 *      无
 **/
void nonTraversal_Before(BiTNode *root)
{
    if (root == NULL)
        return;

    LinkStack *stack = fLinkStack.create();

    while (root || fLinkStack.length(stack) > 0)
    {
        while (root)
        {
            printf("%c ", root->data);
            fLinkStack.push(stack, (LinkStackNode *)root);
            root = root->lchild;
        }
        root = fLinkStack.pop(stack);

        root = root->rchild;
    }

    fLinkStack.destroy(stack);
}

/**
 * 功 能：
 *      二叉树的非递归遍历 - 中序遍历
 * 参 数：
 *      root：要遍历的树
 * 返回值：
 *      无 
 **/
void nonTraversal_Middle(BiTNode *root)
{
    if (root == NULL)
        return;
}

/**
 * 功 能：
 *      二叉树的非递归遍历 - 中序遍历
 * 参 数：
 *      root：要遍历的树
 * 返回值：
 *      无 
 **/
void nonTraversal_Later(BiTNode *root)
{
    if (root == NULL)
        return;
}

/**
 * 功 能：
 *      二叉树的非递归遍历 - 中序遍历
 * 参 数：
 *      root：要遍历的树
 * 返回值：
 *      无 
 **/
void nonTraversal_Level(BiTNode *root)
{
    if (root == NULL)
        return;
}

fNRTraversal traversal = {
    BiTree_Create,
    nonTraversal_Before,
    nonTraversal_Middle,
    nonTraversal_Later,
    nonTraversal_Level};
